package sol.leetcode;

import utils.ArrayUtils;

/**
 * Unique Paths II
 */
public class Issue063 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0)
            return 0;

        //行列值
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] cache = new int[m + 1][n + 1];
        for (int i = 0; i < m + 1; ++i) {
            for (int j = 0; j < n + 1; ++j) {
                if (i == 0 || j == 0)
                    cache[i][j] = 0;
                else if (i == 1 && j == 1)
                    cache[i][j] = obstacleGrid[i - 1][j - 1] == 1 ? 0 : 1;
                else if (obstacleGrid[i - 1][j - 1] == 1)
                    cache[i][j] = 0;
                else
                    cache[i][j] = cache[i - 1][j] + cache[i][j - 1];
            }
        }

        ArrayUtils.print(cache);

        return cache[m][n];
    }

    public static void main(String[] args) {
        int[][] obstacleGrid = {{1,0}
        };

        Issue063 sol = new Issue063();
        System.out.println(sol.uniquePathsWithObstacles(obstacleGrid));
    }
}
